package leetcode_core.leetcode_1;

public class ShipWithinDays {
    public int shipWithinDays(int[] weights, int days) {
        int[] maxAndSum = getMaxAndSum(weights);
        int left = maxAndSum[0],right = maxAndSum[1]+1;
        //定义搜索区间[left,right),right不可达
        while (left<right){
            int mid = left + (right-left)/2;
            if(canFinish(weights,days,mid)){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        return left;
    }
    private int[] getMaxAndSum(int[] weights){
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int weight : weights) {
            max = Math.max(max,weight);
            sum += weight;
        }
        int[] ans = new int[2];ans[0] = max;ans[1]=sum;
        return ans;
    }
    //如果载重为cap,能否在D天内运完货物
    private boolean canFinish(int[] weights,int days,int cap){
        int i = 0;
        for(int day = 0 ;day<days;day++){
            //初始化载重
            int maxCap = cap;//表示这一天的运载量,然后开始装货
            while ((maxCap -= weights[i]) >= 0){//不断装货,一旦<了就是当天的运载量到极限了不能再装了
                i++;
                if(i == weights.length){
                    return true;
                }
            }
        }
        return false;
    }

}
